from math import sqrt


class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        mid_list = [1 for i in range(n)]
        mid_list[0], mid_list[1], i = 0, 0, 2
        try:
            while True:
                try:
                    j = i
                    while True:
                        mid_list[i * j] = 0
                        j += 1
                except:
                    i = mid_list.index(1, i+1)
        except:
            return sum(mid_list)
            # return mid_list.count(1)


class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        mid_list = [1 for i in range(n)]
        mid_list[0], mid_list[1] = 0, 0
        for i in range(2, int(sqrt(n))+1):
            if mid_list[i] == 1:
                mid_list[i * i::i] = [0] * len(mid_list[i * i::i])
        return mid_list.count(1)


a = Solution()
print(a.countPrimes(8))
print(a.countPrimes(10))
print(a.countPrimes(100))
